#pragma once
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<assert.h>

using namespace std;
//
//template<class T>
//struct ListNode
//{
//	T val;
//	ListNode* next;
//
//	ListNode(T value):val(value),next(nullptr)
//	{}
//	ListNode()
//	{}
//};
//
//template<class T>
//class list
//{
//public:
//	list()
//	{
//		phead = new ListNode<T>;
//		phead->next = nullptr;
//		tail = phead;
//	}
//
//	void push_front(T val)
//	{
//		ListNode<T>* tmp = phead->next;
//		ListNode<T>* newnode = new ListNode<T>(val);
//		newnode->next = phead->next;
//		phead->next = newnode;
//		if (tmp == nullptr)	tail = phead->next;
//	}
//
//	void push_back(T val)
//	{
//		ListNode<T>* newnode = new ListNode<T>(val);
//		newnode->next = tail->next;
//		tail->next = newnode;
//		tail = newnode;
//	}
//
//	void pop_front()
//	{
//		if (tail == phead) return;
//		if (tail == phead->next)
//		{
//			delete phead->next;
//			phead->next = nullptr;
//			tail = phead;
//		}
//		else
//		{
//			ListNode<T>* cur = phead->next->next;
//			delete phead->next;
//			phead->next = cur;
//		}
//	}
//
//	void pop_back()
//	{
//		if (tail == phead) return;
//		if (tail == phead->next)
//		{
//			delete phead->next;
//			tail = phead;
//		}
//		else
//		{
//			ListNode<T>* cur = phead;
//			while (cur->next != tail)
//			{
//				cur = cur->next;
//			}
//			delete tail;
//			cur->next = nullptr;
//			tail = cur;
//		}
//	}
//
//	void print()
//	{
//		ListNode<T>* cur = phead->next;
//		while (cur)
//		{
//			cout << cur->val << " ";
//			cur = cur->next;
//		}
//		cout << endl;
//	}
//
//	~list()
//	{}
//private:
//	ListNode<T>* phead;
//	ListNode<T>* tail;
//};

typedef int ValType;
typedef struct ListNode
{
	ValType val;
	struct ListNode* next;
}Node;

Node* get_node(ValType val)
{
	Node* newnode = (Node*)malloc(sizeof(Node));
	newnode->val = val;
	newnode->next = nullptr;
	return newnode;
}

void push_back(Node** pphead, ValType val)
{
	if (*pphead == nullptr)
	{
		*pphead = get_node(val);
		return;
	}
	Node* tail = *pphead;
	while (tail->next)
	{
		tail = tail->next;
	}

	tail->next = get_node(val);
}

void push_front(Node** pphead, ValType val)
{
	if (*pphead == nullptr)
	{
		*pphead = get_node(val);
		return;
	}
	Node* newnode = get_node(val);
	newnode->next = *pphead;
	*pphead = newnode;
}

void pop_front(Node** pphead)
{
	assert(*pphead);
	assert(pphead);
	Node* phead = *pphead;
	Node* tmp = (*pphead)->next;
	free(phead);
	*pphead = tmp;
}

void pop_back(Node** pphead)
{
	assert(*pphead);
	assert(pphead);
	Node* cur = *pphead;
	Node* next = cur->next;
	if (next)
	{
		while (next->next)
		{
			cur = next;
			next = next->next;
		}
		 free(next);
		cur->next = nullptr;
	}
	else
	{
		 free(cur);
		*pphead = nullptr;
	}

}

void insert(Node** pphead, Node* pos, ValType val)
{
	Node* newnode = get_node(val);
	Node* tmp = pos->next;
	pos->next = newnode;
	newnode->next = tmp;
}

void erase(Node** pphead, Node* pos)
{
	assert(*pphead);
	assert(pphead);
	if (*pphead == pos)
	{
		Node* tmp = (*pphead)->next;
		free(pos);
		*pphead = tmp;
	}
	else
	{
		Node* pre = *pphead;
		Node* cur = pre->next;
		while (cur != pos)
		{
			pre = cur;
			cur = cur->next;
		}
		pre->next = pos->next;
		free(cur);
	}
}

	void print(Node* phead)
	{
		Node* cur = phead->next;
		while (cur)
		{
			cout << cur->val << " ";
			cur = cur->next;
		}
		cout << endl;
	}